Broadcast encryption schemes enable a center to deliver encrypted data to a large set of users so that only a particular subset of privileged users can decrypt it. Such schemes are useful in pay-TV systems, the distribution of copyrighted material on encrypted media, and internet multicasting. In one exemplary scenario, authorized pay-per-view customers are provided with so-called “set top boxes” that decrypt the programs in accordance with decryption algorithms inside the boxes. Various billing schemes may be tied to the set-top boxes or other customer identification to ensure that authorized customers are billed for the programs they receive. While effective for blocking access to many non-paying customers, such boxes can be cloned using relatively sophisticated cloning techniques, then sold to people who can then use the clones to watch and/or copy for free the otherwise pay-per-view programs.
Similarly, movie studios are reluctant to distribute protected content via high-definition DVD unless some assurance is provided that only DVD players and recorders made by manufacturers who have agreed to content protection protocols can view or copy the content, and unauthorized recipients can be somehow neutralized. While it is occasionally possible to discover a single receiver or player, most remain undetected in users' homes, leading to a loss of revenue for the broadcasters. This loss of revenue is a growing problem, particularly with the growth of in-home digital video devices, because digital copies are perfect copies. Indeed, the growth of digital video has led to the introduction of a new digital bus standard referred to both as “Firewire” and “IEEE 1394”, which has been proposed to standardize the interconnections between a user's digital television, digital video cassette recorder, digital video disk player, and set-top box. Cellular phones may also be receiver devices.
Because millions of receiver devices might conceivably use the same decryption keys, it is not feasible to individually reprogram each authorized device with new decryption keys. Indeed, the only feasible way to reprogram millions of in-home decryption receivers of encrypted broadcast programs is to broadcast a new encryption key, but then the unauthorized clones also receive the broadcast of the new key, leading to the classic broadcast encryption conundrum: how can authorized receivers be efficiently reprogrammed with new decryption keys while disenfranchising unauthorized clones?
Accordingly, U.S. Pat. No. 6,118,873 provides an encryption system for the secure broadcasting of programs, including updates to authorized in-home digital video devices. That patent discloses a system for encrypting broadcast music, videos, and other content. As set forth therein, only authorized player-recorders can play and/or copy the content and only in accordance with rules established by the vendor of the content. In this way, pirated copies of content, which currently cost content providers billions of dollars each year, can be prevented. As disclosed in the '873 patent, authorized player-recorders are issued software-implemented device keys from a matrix of device keys termed a media key block. The keys can be issued simultaneously with each other or over time, but in any event, no player-recorder is supposed to have more than one device key per column of the matrix. Although two devices might share the same key from the same column, the chances that any two devices share exactly the same set keys from all the columns of the matrix are very small when keys are randomly assigned. The keys are used to decrypt content.
In the event that a device (i.e. its keys) becomes compromised, deliberately or by mistake, it is necessary to revoke the keys of that device. Revoking a set of keys effectively renders the compromised device (and any clones thereof) inoperable to play or record content that is produced after the revocation. The presence of more than a few “rogue” manufacturers (i.e., manufacturers who legally or illegally obtain keys but who in any case make many unauthorized devices having the keys) can be problematic. It is therefore desirable to account for potentially many rogue manufacturers by executing a large number of device revocations. However, since in the '873 system more than one device can share any particular key with the compromised device, revoking a set of device keys might result in revoking keys held by some innocent devices. It is desirable to further reduce the chances of accidentally revoking a “good” device, preferably to zero. It is also desirable to minimize the number and length of key management messages and the amount of storage required by each device.
The latest broadcast encryption technologies designed to meet these goals are based on trees of keys. The so-called “Logical Key Hierarchy” key management system was originally developed independently by Wallner and Wong, cited above. Later, there was the much more concise subset-difference tree, developed at IBM by Naor, Naor, and Lotspiech (NNL) and described in the cited '701 and '906 applications; these applications also describe related traitor tracing schemes (i.e. determining the keys of rogue receivers to enable their revocation while avoiding impacting innocent devices that may share some of the same keys). Most recently, there was an improvement on the NNL subset-difference method by Shamir and Halevy, cited above, that reduced the number of keys required in the device.
It is very convenient if these key trees are “32-bit trees”. That means there are 232 nodes in the tree, and therefore that all the calculations can be performed with 32-bit integer arithmetic, which is a natural number for modern processors. A 32-bit binary tree has 231 leaf nodes; therefore such a tree can support more than two billion individual devices. Two billion seems like a lot of devices, but if a content protection scheme becomes ubiquitous, such that every potential receiver device imaginable supports it, it is not sufficient. Larger key trees are required to support more devices.
For example, a 40-bit tree supports more than enough devices (over 500 billion), but requires awkward 5-byte integer calculations in each device. Even worse, the number of keys that need to be stored in a tree-based scheme is a function of the height of the tree, so that the larger tree requires every device to implement more secure storage for keys. Thus, the following dilemma has heretofore faced designers of content protection schemes based on broadcast encryption: should they risk the convenient 32-bit tree size and hope that their scheme is not too successful, or should they propose a more awkward, expensive scheme whose extra capacity might never be needed. It would be a disaster if a 32-bit tree overflows, because historically one would have to deploy a new, incompatible scheme once it became necessary to support more than two billion devices.